<!DOCTYPE html>
<html lang=zh>
<head><meta name="generator" content="Hexo 3.9.0">
    <!-- so meta -->
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="HandheldFriendly" content="True">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="description" content="前言时隔3个月我又来了，leetcode第二题，大数字相加 问题描述 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digi">
<meta property="og:type" content="website">
<meta property="og:title" content="Two Sum question">
<meta property="og:url" content="https://andyliwr.github.io/others/leetcode/add_two_numbers.html">
<meta property="og:site_name" content="月光倾城的代码小屋">
<meta property="og:description" content="前言时隔3个月我又来了，leetcode第二题，大数字相加 问题描述 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digi">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="https://img.vim-cn.com/28/40dee6d4df70f0a256a2b8e501b7459b1b345c.png">
<meta property="og:image" content="https://img.vim-cn.com/1a/5ffa1d252f1f8c87bf4fccb0ddf865a8d5a55b.jpg">
<meta property="og:updated_time" content="2020-01-15T06:30:09.120Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Two Sum question">
<meta name="twitter:description" content="前言时隔3个月我又来了，leetcode第二题，大数字相加 问题描述 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digi">
<meta name="twitter:image" content="https://img.vim-cn.com/28/40dee6d4df70f0a256a2b8e501b7459b1b345c.png">
    
    
        
          
              <link rel="shortcut icon" href="/images/favicon.ico">
          
        
        
          
            <link rel="icon" type="image/png" href="/images/favicon-192x192.png" sizes="192x192">
          
        
        
          
            <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
          
        
    
    <!-- title -->
    <title>Two Sum question</title>
    <!-- styles -->
    <link rel="stylesheet" href="/css/style.css">
    <!-- persian styles -->
    
      <link rel="stylesheet" href="/css/rtl.css">
    
    <!-- rss -->
    
    
</head>

<body class="max-width mx-auto px3 ltr">
    
    <div class="content index py4">
        
          <header id="header">
  <a href="/">
  
    
      <div id="logo" style="background-image: url(https://file.lantingshucheng.com/1544183173428.ico);"></div>
    
  
    <div id="title">
      <h1>月光倾城的代码小屋</h1>
    </div>
  </a>
  <div id="nav">
    <ul>
      <li class="icon">
        <a href="#"><i class="fas fa-bars fa-2x"></i></a>
      </li>
       
        <li><a href="/">首页</a></li>
       
        <li><a href="/archives/">归档</a></li>
       
        <li><a href="/search/">搜索</a></li>
       
        <li><a href="/tags/">标签</a></li>
       
        <li><a href="/others/">其他文章</a></li>
      
    </ul>
  </div>
</header>

        
        <article class="post" itemscope itemtype="http://schema.org/BlogPosting">
  

  <div class="content" itemprop="articleBody">
      
        <h3 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h3><p>时隔3个月我又来了，leetcode第二题，大数字相加</p>
<h3 id="问题描述"><a href="#问题描述" class="headerlink" title="问题描述"></a>问题描述</h3><blockquote>
<p>You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.<br>You may assume the two numbers do not contain any leading zero, except the number 0 itself.<br>Example:<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition for singly-linked list.</span></span><br><span class="line"><span class="comment"> * function ListNode(val) &#123;</span></span><br><span class="line"><span class="comment"> *     this.val = val;</span></span><br><span class="line"><span class="comment"> *     this.next = null;</span></span><br><span class="line"><span class="comment"> * &#125;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line">Input: (<span class="number">2</span> -&gt; <span class="number">4</span> -&gt; <span class="number">3</span>) + (<span class="number">5</span> -&gt; <span class="number">6</span> -&gt; <span class="number">4</span>)</span><br><span class="line">Output: <span class="number">7</span> -&gt; <span class="number">0</span> -&gt; <span class="number">8</span></span><br><span class="line">Explanation: <span class="number">342</span> + <span class="number">465</span> = <span class="number">807.</span></span><br></pre></td></tr></table></figure></p>
</blockquote>
<p>我的四级英语翻译：</p>
<blockquote>
<p>给定两个用户链表表示的非空数字，数字以相反的顺序存储，每个节点包含一个数字。添加两个数字并将其作为链接列表返回。。<br>您可以假设这两个数字不包含任何前导零，除了数字0本身。。</p>
</blockquote>
<p>这题不愧是中等难度提，把我脑壳都想破了，我的想法是这样，链表在js中好像没搞过呀，但是数字相加跟简单呀，能不能先将链表转化成数字，最后两个数字相加，再讲相加的结果重新转化成链表<br>于是balabala写了两个函数<br><figure class="highlight zephir"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 将ListNode转化成数字</span></span><br><span class="line"><span class="keyword">let</span> transListNodeToNum = <span class="function"><span class="keyword">function</span><span class="params">(listNode)</span> </span>&#123;</span><br><span class="line">  <span class="keyword">let</span> result = <span class="string">''</span></span><br><span class="line">  result = listNode.val + result</span><br><span class="line">  <span class="keyword">if</span> (listNode.next) &#123;</span><br><span class="line">    result = transListNodeToNum(listNode.next) + result</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> result</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 将数字转化成ListNode</span></span><br><span class="line"><span class="keyword">let</span> transNumToListNode = <span class="function"><span class="keyword">function</span><span class="params">(num)</span> </span>&#123;</span><br><span class="line">  <span class="keyword">let</span> result = &#123;&#125;</span><br><span class="line">  <span class="keyword">let</span> <span class="keyword">array</span> = num.split(<span class="string">''</span>).reverse()</span><br><span class="line">  result = <span class="keyword">new</span> ListNode(<span class="keyword">array</span>[<span class="number">0</span>])</span><br><span class="line">  <span class="keyword">if</span> (<span class="keyword">array</span>.length &gt; <span class="number">1</span>) &#123;</span><br><span class="line">     result.next = transNumToListNode(<span class="keyword">array</span>.slice(<span class="number">1</span>).reverse().join(<span class="string">''</span>))</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> result</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>写这两个函数可费了很大力气，一开始想要用遍历去做，发现根本写不下去，于是改成用递归，还真的实现了。<br>最后欢欢乐乐去提交代码，结果出错了<br><img src="https://img.vim-cn.com/28/40dee6d4df70f0a256a2b8e501b7459b1b345c.png" alt="大数字相加错误"><br>原因很简单，Javascript在表示大数字的时候会将其转化成科学计数法，这个时候将数字parseInt就会得到”+“，”e“这些乱七八糟的字符。<br>当然想着将科学计算法的数字转化成正常数字也没用，因为即使使用new Number(xxx)然后在toLocalString转了，精度就会有损失，比如10000000022就变成10000000000，最后两位没了。<br>经过上面的折腾我明白了，使用两个数字直接相加是没用的。然后我想起了之前学习算法的时候不是学了一个大数字相加的算法，于是去翻笔记把它找到了：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">bigNumberAdd</span>(<span class="params">num1, num2</span>) </span>&#123;</span><br><span class="line">  <span class="keyword">if</span> (<span class="built_in">parseInt</span>(num1) + <span class="built_in">parseInt</span>(num2) === <span class="number">10</span>) &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="string">'10'</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">let</span> arr1 = num1.split(<span class="string">''</span>).reverse()</span><br><span class="line">  <span class="keyword">let</span> arr2 = num2.split(<span class="string">''</span>).reverse()</span><br><span class="line">  <span class="keyword">let</span> maxLen = arr1.length &gt; arr2.length ? arr1.length : arr2.length</span><br><span class="line">  <span class="keyword">let</span> result = []</span><br><span class="line">  <span class="keyword">let</span> addNum = <span class="number">0</span></span><br><span class="line">  <span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>; i&lt;maxLen; i++) &#123;</span><br><span class="line">    result[i] = <span class="built_in">parseInt</span>(arr1[i] || <span class="number">0</span>) + <span class="built_in">parseInt</span>(arr2[i] || <span class="number">0</span>) + addNum</span><br><span class="line">    <span class="keyword">if</span> (result[i] &gt;= <span class="number">10</span>) &#123;</span><br><span class="line">      addNum = <span class="number">1</span></span><br><span class="line">      result[i] = result[i] % <span class="number">10</span></span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      addNum = <span class="number">0</span></span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> result.reverse().join(<span class="string">''</span>)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>最后我使用bigNumberAdd去替换两数字直接相加，又重新提交了一遍，发现还是报错了，竟然连<code>[5], [5]</code>这么简单的用例都出错了，结果显示为<code>0</code><br>我就纳闷了不应该是<code>[1,0]</code>吗？结果一检查发现bigNumberAdd的算法是有问题的，bigNumberAdd(5, 5)的结果竟然是0，因为执行过程中maxLen=1，所以循环只执行了一次，所以最后一个1没有附加到result上<br>我意识到是bigNumberAdd算法的问题于是动手改进下:<br><figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">bigNumberAdd</span>(<span class="params">num1, num2</span>) </span>&#123;</span><br><span class="line">  <span class="keyword">let</span> arr1 = num1.split(<span class="string">''</span>).reverse()</span><br><span class="line">  <span class="keyword">let</span> arr2 = num2.split(<span class="string">''</span>).reverse()</span><br><span class="line">  <span class="keyword">let</span> maxLen = arr1.length &gt; arr2.length ? arr1.length : arr2.length</span><br><span class="line">  <span class="keyword">let</span> result = []</span><br><span class="line">  <span class="keyword">let</span> addNum = <span class="number">0</span></span><br><span class="line">  <span class="comment">// 将循环条件改成i&lt;=maxLen，让循环每次多执行一次</span></span><br><span class="line">  <span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>; i&lt;=maxLen; i++) &#123;</span><br><span class="line">    result[i] = <span class="built_in">parseInt</span>(arr1[i] || <span class="number">0</span>) + <span class="built_in">parseInt</span>(arr2[i] || <span class="number">0</span>) + addNum</span><br><span class="line">    <span class="keyword">if</span> (result[i] &gt;= <span class="number">10</span>) &#123;</span><br><span class="line">      addNum = <span class="number">1</span></span><br><span class="line">      result[i] = result[i] % <span class="number">10</span></span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      addNum = <span class="number">0</span></span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="comment">// 因为每次循环都多执行了一次，所以可能会在数字开头多一个0，使用replace将其删除</span></span><br><span class="line">  <span class="keyword">return</span> result.reverse().join(<span class="string">''</span>).replace(<span class="regexp">/^0&#123;1&#125;/g</span>, <span class="string">''</span>)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>至此所有的问题都解决了，重新提交一遍，结果通过了，不过算法的效率评分好低，哈哈<br><img src="https://img.vim-cn.com/1a/5ffa1d252f1f8c87bf4fccb0ddf865a8d5a55b.jpg" alt="编译结果"></p>
<p>偷偷去看了下别人写的算法，不过还没来得及研究，粘贴下代码：<br><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> addTwoNumbers = <span class="function"><span class="keyword">function</span>(<span class="params">l1, l2</span>) </span>&#123;</span><br><span class="line">  <span class="keyword">var</span> l1p = l1; <span class="comment">// list 1 pointer</span></span><br><span class="line">  <span class="keyword">var</span> l2p = l2; <span class="comment">// list 2 pointer</span></span><br><span class="line"></span><br><span class="line">  <span class="keyword">var</span> prev = <span class="keyword">new</span> ListNode(<span class="literal">null</span>);</span><br><span class="line">  <span class="keyword">var</span> prevp = prev; <span class="comment">// prev pointer</span></span><br><span class="line">  <span class="keyword">var</span> carry = <span class="literal">false</span>;</span><br><span class="line">  <span class="keyword">while</span>(l1p || l2p) &#123;</span><br><span class="line">    <span class="keyword">var</span> curr = l1p != <span class="literal">null</span> ? l1p : l2p;</span><br><span class="line">    <span class="keyword">var</span> val1 = l1p != <span class="literal">null</span> ? l1p.val : <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">var</span> val2 = l2p != <span class="literal">null</span> ? l2p.val : <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">var</span> val3 = carry ? <span class="number">1</span>:<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">var</span> sum = val1 + val2 + val3;</span><br><span class="line">    <span class="keyword">if</span>(sum &gt; <span class="number">9</span>) &#123;</span><br><span class="line">      sum = sum - <span class="number">10</span>;</span><br><span class="line">      carry = <span class="literal">true</span>;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">      carry = <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    curr.val = sum;</span><br><span class="line">    prevp.next = curr;</span><br><span class="line">    prevp = prevp.next;</span><br><span class="line">    <span class="keyword">if</span>(l1p) l1p = l1p.next;</span><br><span class="line">    <span class="keyword">if</span>(l2p) l2p = l2p.next;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">if</span>(carry) &#123;</span><br><span class="line">    prevp.next = <span class="keyword">new</span> ListNode(<span class="number">1</span>);</span><br><span class="line">  &#125;   </span><br><span class="line">  <span class="keyword">return</span> prev.next;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<h3 id="心得体会"><a href="#心得体会" class="headerlink" title="心得体会"></a>心得体会</h3><ol>
<li>递归在手，天下我有</li>
<li>大数字相加算法</li>
<li>比我厉害的人还很多很多呀，多努力</li>
</ol>

      
  </div>
</article>

        
        <footer id="footer">
  <div class="footer-left">
    Copyright &copy; 2020 Dikang Li
  </div>
  <div class="footer-right">
    <nav>
      <ul>
         
          <li><a href="/">首页</a></li>
         
          <li><a href="/archives/">归档</a></li>
         
          <li><a href="/search/">搜索</a></li>
         
          <li><a href="/tags/">标签</a></li>
         
          <li><a href="/others/">其他文章</a></li>
        
      </ul>
    </nav>
  </div>
</footer>

    </div>
</body>
</html>
<!-- styles -->
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
<link rel="stylesheet" href="/lib/justified-gallery/css/justifiedGallery.min.css">
<link rel="stylesheet" href="/lib/fancybox/jquery.fancybox.css">

<link rel="stylesheet" href="https://file.lantingshucheng.com/blog/v3/static/styles/gitalk.css">


<!-- jquery -->
<script src="/lib/jquery/jquery.min.js"></script>
<script src="/lib/justified-gallery/js/jquery.justifiedGallery.min.js"></script>
<script src="/lib/fancybox/jquery.fancybox.pack.js"></script>

<script type="text/javascript" src="https://file.lantingshucheng.com/blog/v3/static/scripts/md5.js"></script>
<script type="text/javascript" src="https://file.lantingshucheng.com/blog/v3/static/scripts/gitalk.min.js"></script>

<script src="/js/main.js"></script>
<!-- search -->

<!-- Google Analytics -->

<!-- Baidu Analytics -->

    <script type="text/javascript">
        var _hmt = _hmt || [];
        (function() {
            var hm = document.createElement("script");
            hm.src = "https://hm.baidu.com/hm.js?7851ca7a86be957be994acb77639a5be";
            var s = document.getElementsByTagName("script")[0];
            s.parentNode.insertBefore(hm, s);
        })();
    </script>

<!-- Disqus Comments -->


  <script type="text/javascript">
    window.onload = function(){
      if (window.location.href.indexOf('andyliwr.github.io') > -1) {
        var gitalk = new Gitalk({
          clientID: 'ad6f70df0c70d2b715f9',
          clientSecret: '40384bee244c1e17dd7c37733d21e9ef669e969c',
          repo: 'Andyliwr.github.io',
          owner: 'Andyliwr',
          admin: ['Andyliwr'],
          id: md5(location.pathname),
          distractionFreeMode: 'true'
        })
        gitalk.render('gitalk_thread')
      }
    }
  </script>


